#include "../process.h"
#include "../util.h"
#include "../log/log_mgr.h"
#include "../config.h"
#include <cmath>

int TOTAL_COUNT;	
map<string, set<int>> dim_array;
vector<vector<string>> clusters;
vector<map<string, double>> cluster2centroid;
map<string, int> query2freq;
map<string, map<string, double>> query2feature;
double D_max;

inline void load_query(string &line)
{
	int del1 = line.find("\t"), del2 = line.find("\t", del1 + 1);

	int freq = atoi(line.substr(0, del1).c_str());
	string query = line.substr(del1 + 1, del2 - del1 - 1);
	string feature_s = line.substr(del2 + 1, line.length() - del2 - 1);
	
	vector<string> qf_list = util::tokenize_h(feature_s, "\t");
	map<string, double> feature2value;
	double norm_base = 0;
	for(int i = 0; i < qf_list.size(); ++ i)
	{
		string v_f = qf_list[i];
		int del = v_f.find(":");
		int value = atoi(v_f.substr(0, del).c_str());
		norm_base += (value * value);
		string feature = v_f.substr(del + 1, v_f.length() - del - 1);
		feature2value.insert(pair<string, double>(feature, value));
	}
	query2freq.insert(pair<string, int>(query, freq));
	norm_base = sqrt(norm_base);
	for(map<string, double>::iterator feature2value_itr = feature2value.begin();
		feature2value_itr != feature2value.end();
		++ feature2value_itr)
		(*feature2value_itr).second /= norm_base;
	query2feature.insert(pair<string, map<string, double>>(query, feature2value));
}

inline void init_query(string &line, string &query, vector<string> &url_list)
{
	int del1 = line.find("\t"), del2 = line.find("\t", del1 + 1);

	int freq = atoi(line.substr(0, del1).c_str());
	query = line.substr(del1 + 1, del2 - del1 - 1);
	string feature_s = line.substr(del2 + 1, line.length() - del2 - 1);
	
	vector<string> qf_list = util::tokenize_h(feature_s, "\t");
	map<string, double> feature2value;
	double norm_base = 0;
	for(int i = 0; i < qf_list.size(); ++ i)
	{
		string v_f = qf_list[i];
		int del = v_f.find(":");
		int value = atoi(v_f.substr(0, del).c_str());
		norm_base += (value * value);
		string feature = v_f.substr(del + 1, v_f.length() - del - 1);
		url_list.push_back(feature);
		feature2value.insert(pair<string, double>(feature, value));
	}
	query2freq.insert(pair<string, int>(query, freq));
	norm_base = sqrt(norm_base);
	for(map<string, double>::iterator feature2value_itr = feature2value.begin();
		feature2value_itr != feature2value.end();
		++ feature2value_itr)
		(*feature2value_itr).second /= norm_base;
	query2feature.insert(pair<string, map<string, double>>(query, feature2value));
}

template <typename ELEM_TYPE> 
inline void add_all(set<ELEM_TYPE> &dest, set<ELEM_TYPE> &src)
{
	for(set<ELEM_TYPE>::iterator itr = src.begin();
					itr != src.end();
					++ itr)
		dest.insert(*itr);
}

inline void add_dim_array(string &url, set<int> &c_set)
{
	map<string, set<int>>::iterator dim_array_itr = dim_array.find(url);
	if(dim_array_itr != dim_array.end())
	{
		set<int> &tmp_dim_set = (*dim_array_itr).second;				
		add_all(c_set, tmp_dim_set);
	}
}

inline double get_dist(string query, int cluster_idx)
{
	map<string, double> &q1_feature = (*query2feature.find(query)).second;
	map<string, double> &q2_feature = cluster2centroid[cluster_idx];
	map<string, double>::iterator itr1, itr2;
	double res = 0.0;
	for(itr1 = q1_feature.begin(); itr1 != q1_feature.end(); ++ itr1){
		double val = (*itr1).second;
		itr2 = q2_feature.find((*itr1).first);
		if(itr2 != q2_feature.end())
			val -= (*itr2).second;
		res += (val * val);
	}
	for(itr1 = q2_feature.begin(); itr1 != q2_feature.end(); ++ itr1){
		double val = (*itr1).second;
		itr2 = q1_feature.find((*itr1).first);
		if(itr2 == q1_feature.end())
			res += (val * val);
	}
	return sqrt(res);
}

inline double get_dist(string query1, string query2)
{
	map<string, double> &q1_feature = (*query2feature.find(query1)).second;
	map<string, double> &q2_feature = (*query2feature.find(query2)).second;
	map<string, double>::iterator itr1, itr2;
	double res = 0.0;
	for(itr1 = q1_feature.begin(); itr1 != q1_feature.end(); ++ itr1)
	{
		double val = (*itr1).second;
		itr2 = q2_feature.find((*itr1).first);
		if(itr2 != q2_feature.end())
			val -= (*itr2).second;
		res += (val * val);
	}
	for(itr1 = q2_feature.begin(); itr1 != q2_feature.end(); ++ itr1)
	{
		double val = (*itr1).second;
		itr2 = q1_feature.find((*itr1).first);
		if(itr2 == q1_feature.end())
			res += (val * val);
	}
	return sqrt(res);
}
inline void update_controid(int cluster_idx)
{
	map<string, double> new_centroid;
	vector<string> cluster_elems = clusters[cluster_idx];
	for(int i = 0; i < cluster_elems.size(); ++ i)
	{
		string &cur_query = cluster_elems[i];
		map<string, double> &cur_feature = (*query2feature.find(cur_query)).second;
		map<string, double>::iterator itr1, itr2;
		for(itr1 = cur_feature.begin(); itr1 != cur_feature.end(); ++ itr1)
		{
			string feature = (*itr1).first;
			double val = (*itr1).second;
			itr2 = new_centroid.find(feature);
			if(itr2 == new_centroid.end())
				new_centroid.insert(pair<string, double>(feature, val));
			else
				(*itr2).second += val;
		}
	}
	double norm = 0.0;
	map<string, double>::iterator itr;
	for(itr = new_centroid.begin(); itr != new_centroid.end(); ++ itr)
	{
		(*itr).second /= cluster_elems.size();
		norm += (*itr).second * (*itr).second;
	}
	norm = sqrt(norm);
	for(itr = new_centroid.begin(); itr != new_centroid.end(); ++ itr)
		(*itr).second /= norm;
	cluster2centroid[cluster_idx] = new_centroid;
}

inline int get_sim_set(string &query, set<int> &c_set)
{
	int res = -1;
	double min_dist = INF;
	for(set<int>::iterator itr = c_set.begin();
		itr != c_set.end();
		++ itr)
	{
		double dist = get_dist(query, *itr);
		if( min_dist - dist > INF_SMALL)
		{
			min_dist = dist;
			res = *itr;
		}
	}
	return res;
}

inline double diamter_after_adding(vector<string> &set, string &query)
{
	vector<string> new_set(set);
	new_set.push_back(query);
	double res = 0.0;
	for(int i = 0 ; i < new_set.size(); ++ i)
	{
		for(int j = i + 1; j < new_set.size(); ++ j)
		{
			double dist = get_dist(new_set[i], new_set[j]);
			double sqare_dist = dist * dist;
			res += (sqare_dist + sqare_dist);
		}
	}
	res /= new_set.size();
	res /= new_set.size() > 1?new_set.size() - 1:new_set.size();
	return sqrt(res);
}

inline void add_to_dim(int cluter_idx, string url)
{
	map<string, set<int>>::iterator itr = dim_array.find(url);
	if(itr == dim_array.end())
	{
		set<int> new_set;
		new_set.insert(cluter_idx);
		dim_array.insert(pair<string, set<int>>(url, new_set));
	}
	else
		(*itr).second.insert(cluter_idx);
}

inline void display(iostream* out)
{
	stringstream res;
	for(int i = 0; i < clusters.size(); ++ i)
	{
		stringstream group_info;
		group_info << i << "\t";
		int total = 0;
		map<int, vector<string>> sort_map;
		map<int, vector<string>>::iterator itr;
		int total_q = 0, cur_q = 0;
		for(int j = 0; j < clusters[i].size(); ++ j)
		{
			string query = clusters[i][j];
			total_q ++;
			int freq = (*query2freq.find(query)).second;
			itr = sort_map.find(-freq);
			if(itr == sort_map.end())
			{
				vector<string> v;
				v.push_back(query);
				sort_map.insert(pair<int, vector<string>>(-freq, v));
			}
			else
				(*itr).second.push_back(query);
			total += freq;
			
		}
		for(itr = sort_map.begin(); itr != sort_map.end(); ++ itr)
		{
			int freq = - (*itr).first;
			vector<string> &query_list = (*itr).second;
			for(int j = 0; j < query_list.size(); ++ j)
			{
				string query = query_list[j];
				group_info << query << "\t" << freq;
				if(++ cur_q < total_q)
					group_info << " | ";
			}
		}
		res << total << "\t" << group_info.str() << endl;
	}
	*out << res.str();
}

inline void copy_files(string from, string to)
{
	fstream from_file(from.c_str(), fstream::in);
	fstream to_file(to.c_str(), fstream::out);
	while(!from_file.eof())
	{
		string line;
		getline(from_file, line);
		to_file << line << endl;
	}
	from_file.close();
	to_file.close();
}

#define BATCH 20000
inline void save_model()
{
	fstream dim_array_model("dim_drray.model", fstream::out);
	fstream clusters_model("cluster.model", fstream::out);
	fstream cluster2centroid_model("cluster2centroid.model", fstream::out);
	fstream current_line_model("line_count.model", fstream::out);

	map<string, set<int>>::iterator dim_array_itr;
	for(dim_array_itr = dim_array.begin(); dim_array_itr != dim_array.end(); ++ dim_array_itr)
	{
		dim_array_model << (*dim_array_itr).first << "\t";
		set<int>::iterator dim_array_set_itr;
		for(dim_array_set_itr = (*dim_array_itr).second.begin();
			dim_array_set_itr != (*dim_array_itr).second.end();
			++ dim_array_set_itr)
			dim_array_model << *dim_array_set_itr << "\t";
		dim_array_model << endl;
	}
	dim_array_model.close();

	for(int i = 0; i < clusters.size(); ++ i)
	{
		for(int j = 0; j < clusters[i].size(); ++ j)
			clusters_model << clusters[i][j] << "\t";
		clusters_model << endl;
	}
	clusters_model.close();

	for(int i = 0; i < cluster2centroid.size(); ++ i)
	{
		map<string, double>::iterator feature_itr;
		for(feature_itr = cluster2centroid[i].begin();
			feature_itr != cluster2centroid[i].end();
			++ feature_itr)
			cluster2centroid_model << (*feature_itr).second << ":" << (*feature_itr).first << "\t";
		cluster2centroid_model << endl;
	}
	cluster2centroid_model.close();

	current_line_model << TOTAL_COUNT << endl;
	current_line_model.close();

	copy_files("dim_drray.model", "dim_drray.model.tmp");
	copy_files("cluster.model", "cluster.model.tmp");
	copy_files("cluster2centroid.model", "cluster2centroid.model.tmp");
	copy_files("line_count.model", "line_count.model.tmp");

}

inline void load_model()
{
	fstream dim_array_model("dim_drray.model", fstream::in);
	fstream clusters_model("cluster.model", fstream::in);
	fstream cluster2centroid_model("cluster2centroid.model", fstream::in);
	fstream current_line_model("line_count.model", fstream::in);
	if(!dim_array_model)return;
	while(!dim_array_model.eof())
	{
		string line;
		getline(dim_array_model, line);
		if(line.length() == 0)continue;
		int del = line.find('\t');
		string url = line.substr(0, del);
		string dims_s = line.substr(del + 1, line.length() - del - 1);
		vector<string> dims = util::tokenize(dims_s, "\t");
		set<int> s;
		for(int i = 0 ; i < dims.size(); ++ i)
			s.insert(atoi(dims[i].c_str()));
		dim_array.insert(pair<string, set<int>>(url, s));
	}
	dim_array_model.close();
	while(!clusters_model.eof())
	{
		string line;
		getline(clusters_model, line);
		if(line.length() == 0)continue;
		vector<string> elems = util::tokenize(line, "\t");
		clusters.push_back(elems);
	}
	clusters_model.close();
	while(!cluster2centroid_model.eof())
	{
		string line;
		getline(cluster2centroid_model, line);
		if(line.length() == 0)continue;
		vector<string> elems = util::tokenize(line, "\t");
		map<string, double> elem_set;
		for(int i = 0; i < elems.size(); ++ i)
		{
			int del = elems[i].find(':');
			double value = atof(elems[i].substr(0, del).c_str());
			string url = elems[i].substr(del + 1, elems[i].length() - 1);
			elem_set.insert(pair<string, double>(url, value));
		}
		cluster2centroid.push_back(elem_set);
	}
	cluster2centroid_model.close();
	while(!current_line_model.eof())
	{
		string line_count_s;
		getline(current_line_model, line_count_s);
		if(line_count_s.length() == 0)continue;
		TOTAL_COUNT = atoi(line_count_s.c_str());
	}
	current_line_model.close();
}

int main(int argc, const char* argv[])
{
	fstream input(argv[1], fstream::in);
	fstream output(argv[2], fstream::out);
	fstream config(argv[3], fstream::in);
	Config::load(&config);

	TOTAL_COUNT = 0;
	int count = 0;
	D_max = atof(Config::get("D_max").c_str());
	util::LogMgr::init(argc, argv);
	util::LogMgr::time_start();

	cout << "loading model\n";
	load_model();
	cout << "clustering";
	
	while(count < TOTAL_COUNT && !input.eof())
	{
		string line;		
		getline(input, line);
		if(line.length() == 0)continue;
		if( count %BATCH == 0)
			cout << ".";
		load_query(line);
		count ++;
	}	
	while(!input.eof())
	{
		string line;
		getline(input, line);
		if(line.length() == 0)continue;
		if( TOTAL_COUNT %BATCH == 0)
		{
			save_model();
			cout << ".";
		}
		TOTAL_COUNT ++;
		string query;
		vector<string> url_list;
		init_query(line, query, url_list);
		set<int> c_set;
		for(int i = 0; i < url_list.size(); ++ i)
			add_dim_array(url_list[i], c_set);
		int sim_cluster_idx = get_sim_set(query, c_set);
		if(sim_cluster_idx != -1 && diamter_after_adding(clusters[sim_cluster_idx], query) < D_max)
			clusters[sim_cluster_idx].push_back(query);
		else{
			sim_cluster_idx = clusters.size();
			vector<string> new_cluster;
			new_cluster.push_back(query);
			clusters.push_back(new_cluster);
			cluster2centroid.push_back(map<string, double>());
		}
		update_controid(sim_cluster_idx);
		for(int i = 0; i < url_list.size(); ++ i)
			add_to_dim(sim_cluster_idx, url_list[i]);
	}
	display(&output);
	cout << endl;
	util::LogMgr::time_end();
	input.close();
	output.close();
	return 0;
}
//int main(int argc, const char* argv[])
//{
//	fstream input(argv[1], fstream::in);
//	fstream output(argv[2], fstream::out);
//	fstream config(argv[3], fstream::in);
//	Config::load(&config);
//	D_max = atof(Config::get("D_max").c_str());
//	util::LogMgr::init(argc, argv);
//	util::LogMgr::time_start();
//	int count = 0;
//	while(!input.eof())
//	{
//		string line;
//		getline(input, line);
//		if(line.length() == 0)continue;
//		if(count ++ %BATCH == 0)cout << ".";
//		string query;
//		vector<string> url_list;
//		init_query(line, query, url_list);
//		set<int> c_set;
//		for(int i = 0; i < url_list.size(); ++ i)
//			add_dim_array(url_list[i], c_set);
//		int sim_cluster_idx = get_sim_set(query, c_set);
//		if(sim_cluster_idx != -1 && diamter_after_adding(clusters[sim_cluster_idx], query) < D_max)
//			clusters[sim_cluster_idx].push_back(query);
//		else{
//			sim_cluster_idx = clusters.size();
//			vector<string> new_cluster;
//			new_cluster.push_back(query);
//			clusters.push_back(new_cluster);
//			cluster2centroid.push_back(map<string, double>());
//		}
//		update_controid(sim_cluster_idx);
//		for(int i = 0; i < url_list.size(); ++ i)
//			add_to_dim(sim_cluster_idx, url_list[i]);
//	}
//	display(&output);
//	cout << endl;
//	util::LogMgr::time_end();
//	input.close();
//	output.close();
//	return 0;
//}